package william.recursive;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhangShenao
 * @date 2024/1/8
 * @description <a href="https://leetcode.cn/problems/fibonacci-number/description/">...</a>
 */
public class Leetcode509_斐波那契数 {
    private Map<Integer, Integer> cache = new HashMap<>();

    /**
     * 采用递归思想
     * 递推公式: F(n)=F(n-1)+F(n-2)
     * 采用HashMap保存中间结果,避免重复计算
     * <p>
     * 时间复杂度O(N)
     * 空间复杂度O(N) 额外申请了一个HashMap,长度为n
     */
    public int fib(int n) {
        //边界条件校验
        if (n < 0) {
            return 0;
        }
        //递归终止条件
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        //首先尝试从缓存中查找结果
        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        //递归调用
        int result = fib(n - 1) + fib(n - 2);

        //保存中间结果
        cache.put(n, result);

        return result;

    }
}
